'''
难度 中等
题目链接 https://leetcode.cn/problems/rotate-image/description/
'''

from typing import List

class Solution:
    # 直接使用辅助数组 O(N^2)
    def rotate1(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 初始化一个新的数组 不能直接 matrix_new = matrix 或 matrix_new = matrix[:] 因为是引用拷贝
        matrixNew = [[0] * n for _ in range(n)]
        
        # 循环行
        for i in range(n):
            # 循环列
            for j in range(n):
                # 第一行对应最后一列 列对应的行
                matrixNew[j][n - i -1] = matrix[i][j]
            
        matrix[:] = matrixNew
        # print(matrix)
    
    # 原地旋转
    def rotate2(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        
        # 循环行
        for i in range(n // 2):
            # 循环列
            for j in range((n + 1) // 2):
                # 因为是原地旋转 所以一圈的数据都要交换才能保证没有被覆盖 这一步要画图 一个个对应
                matrix[j][n - i -1],  matrix[n - i -1][n - j - 1], matrix[n - j - 1][i], matrix[i][j] = \
                matrix[i][j], matrix[j][n - i -1], matrix[n - i -1][n - j - 1], matrix[n - j - 1][i]
            
        # print(matrix)

    # 先水平翻转 再对角线翻转 就得到答案了
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        
        # 水平翻转
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = \
                matrix[n - i - 1][j], matrix[i][j]
        
        # 对角线翻转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = \
                matrix[j][i], matrix[i][j]
            
        # print(matrix)
    

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [[[1,2,3],[4,5,6],[7,8,9]]],
        # [[[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]],
    ]
    预期 = [
        [[[7,4,1],[8,5,2],[9,6,3]]],
        [[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]],
    ]
    for k,v in enumerate(参数):
        r = s.rotate(v[0])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))